#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// 最小体力消耗路径
// 你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights
// 其中 heights[row][col] 表示格子 (row, col) 的高度
// 一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) 
// （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动
// 你想要找到耗费 体力 最小的一条路径
// 一条路径耗费的体力值是路径上，相邻格子之间高度差绝对值的最大值
// 请你返回从左上角走到右下角的最小 体力消耗值
// 测试链接 ：https://leetcode.cn/problems/path-with-minimum-effort/

class Solution 
{
public:
    int minimumEffortPath(vector<vector<int>>& heights) 
    {
        // 0：上，1：右，2：下，3：左
        int move[5] = {-1, 0, 1, 0, -1};

        /*
            这里是无关紧要的东西，可以选择忽略，当然你也可以看一下
            表示上下左右四个方向的技巧还有
            int dx[4] = {0, 0, -1, 1};
            int dy[4] = {-1, 1, 0, 0};
            for(int k = 0; k < 4; ++k)
            {
                int nx = x + dx[k], ny = y + dy[k];
            }
        */

        int m = heights.size(), n = heights[0].size();
        const int INF = 0x3f3f3f3f; // 无穷大
        vector<vector<int>> dist(m, vector<int>(n, INF));

        dist[0][0] = 0;
        vector<vector<int>> visited(m, vector<int>(n));
        // first：源点到当前格子的代价，second：x * n + y
        // 这样做的目的是可以利用库中实现的比较器，不用自己重新实现
        // x * n + y 是表示点常用的技巧，将点（x, y）进行压缩
        // 记 pos = x * n + y，则 x = pos / n，y = pos % n 
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({0, 0});
        while(!q.empty())
        {
            auto [c, pos] = q.top();
            q.pop();
            int x = pos / n, y = pos % n;
            if(visited[x][y]) continue;

            // 常见剪枝
            // 发现终点直接返回
            // 不用等都结束
            if(x == m - 1 && y == n - 1) return c;
            visited[x][y] = true;
            for(int i = 0; i < 4; ++i)
            {
                int nx = x + move[i], ny = y + move[i + 1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny])
                {
                    int nc = max(c, abs(heights[x][y] - heights[nx][ny]));
                    q.push({nc, nx * n + ny});
                }
            }
        }
        return -1;
    }
};